// 给定一个非负整数数组nums，数组中每个元素代表在该位置可以跳跃的最大长度
// 开始位置为数组的第一个下标处，要求判断是否能够到达最后一个下标
// 思路，贪心
// 部最优：每次取最大跳跃步数
// 整体最优：最后得到整体最大覆盖范围，能否覆盖终点
function canJump(nums) {
    let cover = 0
    for (let i = 0; i <= cover; i++) {
        cover = Math.max(cover, nums[i] + i)
        if (cover >= nums.length - 1) {
            return true
        }
    }
    return false
}

// console.log(canJump([2,3,1,1,4]))
console.log(canJump([3,2,1,0,4]))

// 思路2，动态规划
// dp[i]，表示从0触发，经过j <= i，可以跳出的最远距离
// 1. dp[0] = nums[0],表示从0出发，经过0，可以跳出的最远距离为nums[0]
// 2. 如果能通过0~i-1个位置到达i，即dp[i-1]>=i， 则dp[i] = max(dp[i-1], i + nums[i])
// 3. 如果不能通过0~i-1个位置到达i，则dp[i-1] < i, 则dp[i] = dp[i-1]

function canJump2(nums) {
    let dp = new Array(nums.length).fill(0)
    dp[0] = nums[0]
    for (let i = 1; i < nums.length; i++) {
        if (dp[i-1] >= i) {
            dp[i] = Math.max(dp[i-1], nums[i] + i)
        } else {
            dp[i] = dp[i-1]
        }
    }
    return dp[nums.length - 1] >= nums.length - 1
}

console.log(canJump2([2,3,1,1,4]))